package leetcode

func findMedianSortedArraysMethod1(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	midLeft, midRight := 0, 0
	length := m + n
	mid, odd := length/2, length%2
	var union []int

	if m == 0 {
		union = nums2
	}
	if n == 0 {
		union = nums1
	}

	if union == nil {
		union = make([]int, mid+1)
		a, b := 0, 0
		for i := 0; i < mid+1; i++ {
			if a >= m {
				union[i] = nums2[b]
				b++
				continue
			}
			if b >= n {
				union[i] = nums1[a]
				a++
				continue
			}

			if nums2[b] < nums1[a] {
				union[i] = nums2[b]
				b++
			} else {
				union[i] = nums1[a]
				a++
			}
		}
	}

	if odd == 0 {
		midLeft, midRight = union[mid-1], union[mid]
	} else {
		midLeft, midRight = union[mid], union[mid]
	}

	return float64(midLeft+midRight) / 2
}

func findMedianSortedArraysMethod2(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	midLeft, midRight := 0, 0
	length := m + n
	mid, odd := length/2, length%2 == 1

	if m == 0 {
		midLeft, midRight = getMidNums(nums2, mid, odd)
		return float64(midLeft+midRight) / 2
	}
	if n == 0 {
		midLeft, midRight = getMidNums(nums1, mid, odd)
		return float64(midLeft+midRight) / 2
	}

	a, b := 0, 0
	for i := 0; i < mid+1; i++ {
		midLeft = midRight
		if a >= m {
			midRight = nums2[b]
			b++
			continue
		}
		if b >= n {
			midRight = nums1[a]
			a++
			continue
		}

		if nums2[b] < nums1[a] {
			midRight = nums2[b]
			b++
		} else {
			midRight = nums1[a]
			a++
		}
	}
	if odd {
		midLeft = midRight
	}

	return float64(midLeft+midRight) / 2
}

func findMedianSortedArraysMethod3(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	midLeft, midRight := 0, 0
	length := m + n
	mid, odd := length/2, length%2 == 1

	if m == 0 {
		midLeft, midRight = getMidNums(nums2, mid, odd)
		return float64(midLeft+midRight) / 2
	}
	if n == 0 {
		midLeft, midRight = getMidNums(nums1, mid, odd)
		return float64(midLeft+midRight) / 2
	}

	a, b := 0, 0
	for i := 0; i < mid+1; i++ {
		midLeft = midRight
		if a == m {
			midRight = nums2[mid-m]
			if odd {
				midLeft = midRight
			} else if i < mid {
				midLeft = nums2[mid-m-1]
			}
			return float64(midLeft+midRight) / 2
		}
		if b == n {
			midRight = nums1[mid-n]
			if odd {
				midLeft = midRight
			} else if i < mid {
				midLeft = nums1[mid-n-1]
			}
			return float64(midLeft+midRight) / 2
		}

		if nums2[b] < nums1[a] {
			midRight = nums2[b]
			b++
		} else {
			midRight = nums1[a]
			a++
		}
	}
	if odd {
		midLeft = midRight
	}

	return float64(midLeft+midRight) / 2
}

func findMedianSortedArraysMethod4(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	midLeft, midRight := 0, 0
	mid, odd := (m+n)/2, (m+n)%2 == 1

	if m == 0 {
		midLeft, midRight = getMidNums(nums2, mid, odd)
		return float64(midLeft+midRight) / 2
	}
	if n == 0 {
		midLeft, midRight = getMidNums(nums1, mid, odd)
		return float64(midLeft+midRight) / 2
	}

	a, b := 0, 0
	for a+b < mid+1 {
		midLeft = midRight
		if a == m {
			midRight = nums2[mid-m]
			if odd {
				midLeft = midRight
			} else if a+b < mid {
				midLeft = nums2[mid-m-1]
			}
			return float64(midLeft+midRight) / 2
		}
		if b == n {
			midRight = nums1[mid-n]
			if odd {
				midLeft = midRight
			} else if a+b < mid {
				midLeft = nums1[mid-n-1]
			}
			return float64(midLeft+midRight) / 2
		}

		if nums2[b] < nums1[a] {
			midRight = nums2[b]
			b++
		} else {
			midRight = nums1[a]
			a++
		}
	}
	if odd {
		midLeft = midRight
	}

	return float64(midLeft+midRight) / 2
}

func findMedianSortedArraysMethod5(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	midLeft, midRight := 0, 0
	length := m + n
	mid, odd := length/2, length%2 == 1

	a, b := 0, 0
	for i := 0; i < mid+1; i++ {
		midLeft = midRight
		if a == m {
			midRight = nums2[mid-m]
			if odd {
				midLeft = midRight
			} else if i < mid {
				midLeft = nums2[mid-m-1]
			}
			return float64(midLeft+midRight) / 2
		}
		if b == n {
			midRight = nums1[mid-n]
			if odd {
				midLeft = midRight
			} else if i < mid {
				midLeft = nums1[mid-n-1]
			}
			return float64(midLeft+midRight) / 2
		}

		if nums2[b] < nums1[a] {
			midRight = nums2[b]
			b++
		} else {
			midRight = nums1[a]
			a++
		}
	}
	if odd {
		midLeft = midRight
	}

	return float64(midLeft+midRight) / 2
}

func getMidNums(nums []int, mid int, odd bool) (midLeft, midRight int) {
	if odd {
		midLeft, midRight = nums[mid], nums[mid]
	} else {
		midLeft, midRight = nums[mid-1], nums[mid]
	}
	return midLeft, midRight
}
